#ifndef TACORES_FINDAUGMENTINGPATH_H
#define TACORES_FINDAUGMENTINGPATH_H

using namespace std;

#include "FlowNetwork.h"
#include <vector>
#include <list>

class FindAugmentingPath
{
public:
	FindAugmentingPath(FlowNetwork& network)
		: network(network) {}

	bool find(vector<VertexInfo>& vertices)
	{
		vertices[network.sourceIndex] = VertexInfo(-1);
		list<int> path;
		path.push_back(network.sourceIndex);

		vector<VertexStructure>& structure = network.getVertexStructure();
		while(!path.empty())
		{
			int u = path.front(); path.pop_front();

			list<EdgeInfo>::iterator end = structure[u].forwardEnd();
			while(list<EdgeInfo>::iterator it = structure[u].forward(); it != end; ++it)
			{
				EdgeInfo edge = *it;
				int v = edge.end;
				if(vertices[v].isValid() == false && edge.capacity > edge.flow)
				{
					vertices[v] = VertexInfo(u);
					if(v == network.sinkIndex)
					{
						return true;
					}
					path.push_back(v);
				}
			}

			end = structure[u].backwardEnd();
			while(list<EdgeInfo>::iterator it = structure[u].backward(); it != end; ++it)
			{
				EdgeInfo edge = *it;
				int v = edge.start;
				if(vertices[v].isValid() == false && edge.flow > 0)
				{
					vertices[v] = VertexInfo(u, false);
					path.push_back(v);
				}
			}
		}
		return false;
	}

private:
	FlowNetwork& network;
};

#endif

